#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937 rnd(31910);
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}
#include "game.h"

int n;
vector<int>ans,a;
int num;
const int N=5005;

int query(vector<int>q)
{
	int res=count(q);
	if (res==n) ans=q;
	return res;
}
bool vis[N];
int find(int x,int y,int k)
{
	vector<int>tmp;
	rep(i,0,n-1) if (vis[i]==k&&x!=i&&i!=y) tmp.pb(i);
	if (SZ(tmp)==0) return -1;
	int z=rnd()%SZ(tmp);
	return tmp[z];
}

vector<int> guess(int _n, int limit) 
{
	n=_n;
	ans.clear();
	a.resize(n);
	rep(i,1,n) a[i-1]=i;
	shuffle(a.begin(),a.end(),rnd);
	num=query(a);
	rep(i,1,50)
	{
		vector<int>b=a;
		shuffle(a.begin(),a.end(),rnd);
		int tmp=query(a);
		if (tmp>num) num=tmp;
		else swap(a,b);	
	}
	rep(i,0,n-1) vis[i]=0;
	while (SZ(ans)==0)
	{
		vector<int>st;
		rep(i,0,n-1) if (vis[i]==0) st.pb(i);
		int x=rnd()%SZ(st),y=rnd()%SZ(st);
		if (SZ(st)==2) x=0,y=1;
		if (x==y) continue;
		x=st[x],y=st[y];
		// for (int i:a) cout << i << " ";
		// cout << endl;
		// rep(i,0,n-1) cout << vis[i] << " ";
		// cout << endl;
		// cout << x << " " << y << endl;
		if (SZ(st)==2)
		{
			swap(a[x],a[y]);
			return a;
		}
		swap(a[x],a[y]);
		int z=query(a);
		if (z==num) continue;
		if (z==num+2)
		{
			num=z;
			vis[x]=1,vis[y]=1;
			continue;
		}
		if (z==num-2)
		{
			vis[x]=1,vis[y]=1;
			swap(a[x],a[y]);
			continue;
		}
		while (1)
		{
			bool F=0;
			int p=find(x,y,1);
			if (p==-1) F=1,p=find(x,y,0);
			if (z==num-1)
			{
				swap(a[x],a[y]);
				swap(z,num);
			}
			//cout << "p=" << p << endl;
			swap(a[x],a[p]);
			int val=query(a);
			if (F==1)
			{
				if (val<z)
				{
					//cout << "!!!\n";
					swap(a[x],a[p]);
					//vis[x]=1;
					num=z;
					break;
				}
				else
				{
					//swap(a[x],a[p]);
					vis[y]=1;
					if (val==z+2) vis[x]=1,vis[p]=1;
					num=val;
					break;
				}			
			}
			else
			{
				if (val==z-2)
				{
					//cout << "!!!\n";
					swap(a[x],a[p]);
					vis[x]=1;
					num=z;
					break;
				}
				else
				{
					swap(a[x],a[p]);
					vis[y]=1;
					num=z;
					break;
				}		
			}
				
		}
	}
	return ans;
}
